/*
 * TCCC 2003 Semifinals 4 Prob 1
 */

import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;


public class Circuits
{
    public int howLong(String[] connects, String[] costs)
    {
	int n = connects.length;
	ArrayList<ArrayList<Integer>> adjlist = new ArrayList<ArrayList<Integer>> ();
	for (int i = 0; i < n; ++i)
	    adjlist.add (new ArrayList<Integer> ());
	int[][] cost = new int[n][n];
	for (int i = 0; i < n; ++i) {
	    if (connects[i].length () == 0)
		continue;
	    String[] tmp1 = connects[i].split (" ");
	    String[] tmp2 = costs[i].split (" ");
	    for (int t = 0; t < tmp1.length; ++t) {
		int j = Integer.parseInt (tmp1[t]), c = Integer.parseInt (tmp2[t]);
		cost[i][j] = c;
		adjlist.get (i).add (j);
	    }
	}
	int ans = -1;

	for (int i = 0; i < n; ++i) {
	    LinkedList<Integer> stack = new LinkedList<Integer> ();
	    int[] dis = new int[n];
	    Arrays.fill (dis, -1);
	    dis[i] = 0;
	    if (dis[i] > ans)
		ans = dis[i];
	    stack.addLast (i);

	    while (!stack.isEmpty ()) {
		int d = stack.removeLast ();
		for (int next:adjlist.get (d)) {
		    stack.addLast (next);
		    dis[next] = Math.max (dis[next], dis[d]+cost[d][next]);
		    if (dis[next] > ans)
			ans = dis[next];

		}
	    }
	}
	return ans;
    }
    

}
//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!